#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

/*
John 他有 K 个要完成的工作，分给农场里的 N 头奶牛。K = 2N

John 就给每头牛分配两个任务，每头牛只能做完一个任务之后再做另外一个任务。

给定一个 K 个元素的数组，这个数组里是每个任务完成的时间
 0  1  2  3  4  5
[1, 3, 5, 3, 1, 4] k=6 k/2 - 1 = 2
[1, 1, 3, 3, 4, 5]
编写一个函数，计算所有任务完成时间最短的时候，每个任务的分配方式。返回一个二维数组，这个二维数组里的每一项是分配任务的索引。

[
  [0, 2],
  [4, 5],
  [1, 3]
]

1. 如何分配任务时间最短？
1.1 任务数组排序
1.2 头尾分组

2. 如何记录分配方式？
*/

// 返回完成时间最少的情况下，任务耗时的分组
// [1, 3, 5, 3, 1, 4]
//                   

// [1, 1, 3, 3, 4, 5]
//  ^l_task        ^r_task
// 字典
// 汉字字典： 字母（Key 键） -> 中文文字（Value 值），K-V 的集合
// 字典：
/*
  遍历并记录原始 tasks 数组中每个值的位置
  Key  ->   Value
  数组值     数组元素的位置
  1    ->   {0, 4}
  3    ->   {1, 3}
  5    ->   {2}
  4    ->   {5}

  unordered_map<int, vector<int>>
*/
unordered_map<int, vector<int>> getTaskIndices(const vector<int> &tasks) {
  unordered_map<int, vector<int>> result;

  for (int i = 0; i < tasks.size(); ++i) {
    if (result.find(tasks[i]) != result.end()) {
      // 字典中包含 tasks[i]
      result[tasks[i]].push_back(i);
    }
    else {
      // 字典中不包含 tasks[i]
      result[tasks[i]] = {i};
    }
  }

  return result;
}


vector<vector<int>> task_assignment(vector<int> tasks) {
  vector<int> tasks_copy = tasks;
  sort(tasks_copy.begin(), tasks_copy.end());
  vector<vector<int>> result;

  // records - 每一个任务在原始数组中的位置
  unordered_map<int, vector<int>> records = getTaskIndices(tasks);

  int l = 0, r = tasks.size() - 1;

  while (l < r) {
    // 得到排序后左右两边任务的完成时间
    int l_task = tasks_copy[l];
    int l_index = records[l_task].back();
    records[l_task].pop_back();

    int r_task = tasks_copy[r];
    int r_index = records[r_task].back();
    records[r_task].pop_back();

    // 得到 l_task 和 r_task 这两个时间在排序前的数组中的位置
    // l_index 和 r_index
    //
    result.push_back({l_index, r_index});

    ++l;
    --r;
  }

  return result;
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<int> tasks {1, 3, 5, 3, 1, 4};

  auto dictionary = getTaskIndices(tasks);

  for (auto record : dictionary) {
    // record.first -> Key
    // record.second -> Value
    cout << record.first << ":" << "[";

    for (int n : record.second) {
      cout << n << " ";
    }

    cout << "]" << endl;
  }

  
  return 0;
}
